//-------采用十字链表构造有向图------
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
typedef int Status;
typedef char VertexType;
typedef int InfoType;
 
// 定义弧结点结构体
typedef struct ArcBox {
    int tailvex, headvex;           // 该弧的尾和头顶点的位置
    struct ArcBox *hlink, *tlink;  // 分别为弧头相同和弧尾相同的链
    InfoType *info;                // 该弧相关信息的指针
} ArcBox;
 
// 定义顶点结构体
typedef struct VexNode {
    VertexType data;               // 顶点信息
    ArcBox *firstin, *firstout;    // 分别指向该顶点第一条入弧和出弧
} VexNode;
 
// 定义十字链表图结构
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM]; // 表头向量
    int vexnum, arcnum;            // 当前的顶点数和弧数
} OLGraph;
 
// 查找顶点在图中的位置
int LocateVex(OLGraph *G, char v) {
    for (int i = 0; i < G->vexnum; i++) {
        if (G->xlist[i].data == v) {
            return i;
        }
    }
    return -1; // 如果未找到顶点，返回 -1
}
 
// 创建有向图的函数
Status CreateDG(OLGraph *G) {
    int i, j, k;
    char v1, v2; // 输入的两个顶点
    ArcBox *p;
 
    printf("请输入总顶点数和总弧数：\n");
    scanf("%d %d", &G->vexnum, &G->arcnum); // 输入顶点数和弧数
    getchar(); // 清除缓冲区中的换行符
 
    printf("请输入每个顶点的信息（字符形式）：\n");
    for (i = 0; i < G->vexnum; i++) {
        printf("顶点 %d: ", i + 1);
        scanf("%c", &G->xlist[i].data); // 输入顶点信息
        getchar(); // 清除缓冲区中的换行符
        G->xlist[i].firstin = NULL;
        G->xlist[i].firstout = NULL;
    }
 
    printf("请输入每条弧的信息（顶点 v1 和 v2，例如 A B）：\n");
    for (k = 0; k < G->arcnum; k++) {
        printf("弧 %d: ", k + 1);
        scanf(" %c %c", &v1, &v2); // 输入弧的两个顶点
        i = LocateVex(G, v1); // 查找 v1 在图中的位置
        j = LocateVex(G, v2); // 查找 v2 在图中的位置
 
        if (i == -1 || j == -1) {
            printf("顶点输入有误！\n");
            return ERROR;
        }
 
        // 创建弧结点
        p = (ArcBox *)malloc(sizeof(ArcBox));
        p->tailvex = i; // 弧的尾顶点位置
        p->headvex = j; // 弧的头顶点位置
 
        // 插入到 v2 顶点的入弧链表
        p->hlink = G->xlist[j].firstin;
        G->xlist[j].firstin = p;
 
        // 插入到 v1 顶点的出弧链表
        p->tlink = G->xlist[i].firstout;
        G->xlist[i].firstout = p;
 
        p->info = NULL; // 相关信息指针设为 NULL
    }
    return OK;
}
 
// 打印图的十字链表表示
void PrintGraph(OLGraph *G) {
    printf("图的十字链表表示如下：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("顶点 %c 的出弧：", G->xlist[i].data);
        ArcBox *p = G->xlist[i].firstout;
        while (p) {
            printf("-> %c", G->xlist[p->headvex].data);
            p = p->tlink;
        }
        printf("\n");
 
        printf("顶点 %c 的入弧：", G->xlist[i].data);
        p = G->xlist[i].firstin;
        while (p) {
            printf("-> %c", G->xlist[p->tailvex].data);
            p = p->hlink;
        }
        printf("\n");
    }
}
 
// 主函数
int main() {
    OLGraph G;
 
    if (CreateDG(&G) == OK) {
        printf("有向图创建成功！\n");
        PrintGraph(&G);
    } else {
        printf("有向图创建失败！\n");
    }
 
    return 0;
}